package BackTrackingPackage;

import org.junit.jupiter.api.Test;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * @author Lzm
 * @version 1.0
 */
/*没有index, 每当取到list中有的数时,就跳过
* 如 list = [1]
* 取[1,2,3]
* 如果取到了 1,就跳过
* 如果list=[1,2]
* 取[1,2,3]
* 如果取到了 1或2 则跳过*/
public class permute_ {
  LinkedList<Integer> list = new LinkedList<>();
  List<List<Integer>> result = new LinkedList<>();

  @Test
  public void permuteTest(){
    int[] nums = new int[]{1,2,3};
    backTracking(nums);
    System.out.println(result);
  }
  public void backTracking(int[] nums){
    if (list.size() == nums.length){
      result.add(new LinkedList<>(list));
      return;
    }
    Set<Integer> set = new HashSet<>();
    for (int i = 0 ; i < nums.length ; i++){
      if (list.contains(nums[i])){
        continue;
      }
      else{
        set.add(nums[i]);
        list.add(nums[i]);
        backTracking(nums);
        list.removeLast();
      }

    }
  }
}
